#include <stdio.h>
#include "CreateBTree.h"

void displayElement(BNode *elem) {
    printf("%d ", elem->data);
}

//先序遍历（递归实现）
void preOrderTraverse(BTree T) {
    if (T) {
        displayElement(T);
        preOrderTraverse(T->lchild);
        preOrderTraverse(T->rchild);
    }
}

//top变量表示栈顶元素所在位置
int top = -1;

//进栈函数
void push(BNode **a, BNode *elem) {
    a[++top] = elem;
}

//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}

//拿到栈顶元素
BNode *getTop(BNode **a) {
    return a[top];
}

//先序遍历(栈实现)
void preOrderTraverseStack(BTree T) {
    BNode *a[20];
    BNode *p;
    //根节点进栈
    push(a,T);
    while (top!=-1) {
        //获取栈顶元素
        p= getTop(a);
        pop();
        while (p) {
            //打印节点
            displayElement(p);
            //如果该节点有右孩子，右孩子进栈
            if(p->rchild) {
                push(a,p->rchild);
            }
            //一直指向根节点的最后一个左孩子
            p=p->lchild;
        }
    }
}

int main() {
    printf("Hello, World!\n");
    BTree Tree;
    CreateBTree(&Tree);
    printf("先序遍历(递归): \n");
    preOrderTraverse(Tree);
    printf("\n");
    printf("先序遍历(栈): \n");
    preOrderTraverseStack(Tree);
    return 0;
}
